import java.util.ArrayList;
import java.util.List;

/**
 * 784. 字母大小写全排列
 * https://leetcode-cn.com/problems/letter-case-permutation/
 */
public class Solutions_784 {
    public static void main(String[] args) {
        String str = "a1b2";  // output: {"a1b2", "a1B2", "A1b2", "A1B2"}
//        String str = "3z4";  // output: {"3z4", "3Z4"}
//        String str = "12345";  // output: {"12345"}

        List<String> result = letterCasePermutation(str);
        System.out.println(result);
    }

    private static List<String> res = null;
    public static List<String> letterCasePermutation(String S) {
        res = new ArrayList<>();
        char[] arr = S.toCharArray();
        dfs(arr, 0);
        return res;
    }

    /**
     * 解法二：递归自顶向下
     */
    public static void dfs(char[] arr, int index) {
        for (int i = index; i < arr.length; i++) {
            if (arr[i] >= 'a' && arr[i] <= 'z') {
                // 改变状态：小写变大写
                arr[i] ^= 32;
                // 操作之后，向下递归
                dfs(arr, i + 1);
                // 还原状态
                arr[i] ^= 32;
            } else if (arr[i] >= 'A' && arr[i] <= 'Z') {
                // 改变状态：大写变小写
                arr[i] ^= 32;
                // 操作之后，向下递归
                dfs(arr, i + 1);
                // 还原状态
                arr[i] ^= 32;
            }
        }
        // 字符数组遍历结束，添加字符串到结果集中
        res.add(String.valueOf(arr));
    }

    /**
     * 解法一：递归自底向上
     * 树形问题，首先递归到叶子后，往上移动
     * 若满足条件，则从该位置再次递归到叶子
     */
    public static void dfs2(char[] arr, int index) {
        if (index == arr.length) {
            res.add(String.valueOf(arr));
            return;
        }
        // 首先递归到底部，即数组结尾
        dfs2(arr, index + 1);
        if (Character.isLetter(arr[index])) {
            // 当前字符是字母时，大小写互换
            arr[index] ^= 32;
            dfs2(arr, index + 1);
        }
    }
}
